;; Programa: Package con agentes jugadores presa de PlanTron
;;           contra depredadores basados en búsquedas con
;;           sistemas de producción
;;
;;
;; Asignatura: Inteligencia Artificial e Ingeniería del Concimiento
;;             ETSII - ULL 
;; Práctica: Búsquedas 
;; Autores:  aluXXXX y aluYYYY ([Indica aquí nombres completos])
;; Fecha:    27/09/2012
;; Comentarios:
;;
;;           Este código supone un esqueleto de ejemplo de el
;;           fichero que ha de contener los agentes jugadores
;;           de PlanTron que el usuario defina y usen búsqueda
;;           en sistemas de producción.
;;
;;           Para personalizar este fichero ha de renombrarse,
;;           sustituyendo "alu2434-2517" por lo que desee. Además
;;           en este código ha de reemplazarse dondequiera que
;;           apareza "alu2434-2517" o "ALU2434-2517" por lo mismo,
;;           el nombre del fichero sin extensión y el nombre
;;           del package aquí incluido han de coincidir (no
;;           sensitivo a mayúsculas).
;;
;;           Para añadir más agentes habrán de generarse las
;;           funciones correspondientes para los agentes, e 
;;           incluirlas como nuevo agente mediante el uso de
;;           la macro DEFAGENTE. Para más información consultar
;;           ejemplos de "pt-agentes-simples.lisp" y la documentación
;;           (DESCRIBE) de las constantes, variables y funciones allí
;;           utilizadas.
;;
;;           Los agentes definidos utilizan el entorno de juego
;;           PlanTron, definido principalmente por los packages
;;           PT, PT-BASE y ENVIO.
;;
;;           Las funciones accesibles más importantes son:
;;
;;             ALU2434-2517-PRESA-BA: Agente PlanTron que busca
;;             el camino a lugar lejos de depredador mendiante
;;             búsqueda en anchura
;;
;;             ALU2434-2517-PRESA-A: Agente PlanTron que busca
;;             el camino a lugar lejos de depredador mendiante
;;             búsqueda en A*
;;
;;           Ver la documentación existente para cada una de ellas.
;;
;;           Para su utilización es aconsejable usar el cargador
;;           del entorno de juego PlanTron: "pt-loader.lisp".
;;
;;
;; Dependencias:
;;
;;           Hace uso del paquete que contiene la interface (ENVIO)
;;           con el control del juego (PT-BASE).
;;
;;           Hace uso del paquete PT-UTIL con agentes pasivos
;;           con distintas utilidades para asistir a agentes jugadores
;;           de PlanTron (agente pasivo CONTADOR) e interfaces para
;;           acceso a paquetes SHELL, GENERIC-SEACH y A_STAR.
;;
;;           Hace uso del paquete interfaz para la creación de sistemas
;;           de producción simples (SHELL) a través de PT-UTIL.
;;
;;           Hace uso de la función AGENTE-ESPIRAL del paquete
;;           PT-AGENTES-SIMPLES.
;;
;;           Hace uso del paquete marco genérico para la búsquedas en
;;           sistemas de producción simples (GENERIC-SEARCH) a través
;;           de PT-UTIL.
;;
;;           Hace uso del paquete para la búsquedas A* (A_STAR) en
;;           sistemas de producción simples a través de PT-UTIL
;;
;;           Hace uso inderecto del paquete PT-VIS mediante la
;;           solicitud de impresión del camino encontrado en la
;;           función PRINT-CAMINO.
;;
;;
;; Modificaciones:
;;
;;           - Ver 0.1 (27/09/2012): Primera versión
;;
;;
;; Por hacer:
;;
;;
;;           - Posibles mejoras en funcionalidades a implementar
;;             -------------------------------------------------
;;           - Llegado al límite de tiempo usar camino a lugar
;;             encontrado más alejado de depredador
;;               Dificultad: Fácil; Mejora esperada: Poca
;;           - Cuando está lejos del depredador mover con otro agente
;;               Dificultad: Fácil; Mejora esperada: Poca a media
;;           - Que *dist-obj* aumente o disminuya, según encuentre
;;             o no caminos (se autoadapte)
;;               Dificultad: Fácil; Mejora esperada: Media
;;           - Que caminos objetivos sean largos, para evitar
;;             auto-encerrarse y/o sobrevivir más tiempo
;;               Dificultad: Fácil; Mejora esperada: Media a alta
;;           - Usar otra estrategias heurística de búsqueda
;;               Dificultad: Media; Mejora esperada: Media
;;           - Usar tratamiento de estados visitados
;;               Dificultad: Depende, media o difícil
;;               Mejora esperada: Media a alta
;;           - Preferir caminos que pasen sobre más plantas
;;               Dificultad: Media; Mejora esperada: Media
;;           - Cuando está lejos del depredador usar estrategia de 
;;             búsqueda de camino a plantas
;;               Dificultad: Depende, media o difícil
;;               Mejora esperada: Media
;;           - Reutilizar base de hechos de búsquedas anteriores
;;               Dificultad: Depende, difícil a muy difícil
;;               Mejora esperada: Media
;;
;;


;;
;; Definición del package
;; ----------------------

(defpackage "AGENTES-ALU2434-2517-PRESA"
  (:use "COMMON-LISP")
  (:documentation "Agentes jugadores de PlanTron basado en búsquedas.")
  (:export "VERSION" "HACES-PODAR-FN"))

(in-package "AGENTES-ALU2434-2517-PRESA")


;;
;; Constante versión
;; -----------------

(defconstant version "0.1"
  "Versión del package AGENTES-ALU2434-2517-PRESA.")


;;
;; Definición de estructura de estados
;; -----------------------------------


(defstruct estado
  "Almacena los estados del sistema de producción para presas."
  (camino nil)       ; Camino como lista inversa de posiciones (x y)
  (lon-camino 0)     ; Longitud del camino
  (f-heur 0)         ; Valor de la función heurística f'
  (dir-ini nil)      ; Dirección inicial del camino: [nil, 0, 1, 2 ó 3]
  (celdas-vacias 0)  ; Número de casillas vacias pisadas en la búsqueda. G para la heurística de A*
  (fw 0))            ; Heuristica para el AnyTime
;;
;; Definición de varialbes globales
;; --------------------------------

(defvar *f-heur* nil
  "Función heurística que evalua un estado en acción de regla.")

(defvar *estado-objetivo-a-p* nil
"Función estado objetivo para la implementación de A*. Esta función dependerá de si hay que huir o comer.")

(defvar *estado-objetivo-aaw-p* nil
  "Función estado objetivo para la implementación de anytime. Esta función dependerá de si hay que huir o comer.")

(defvar *dist-obj* nil
  "Distancia a la que debe estar el agente presa del depredador para cumplir su objetivo.")

(defvar *id-dpdd* 1
  "Identificador del agente depredador.")

(defvar *min-dist-obj* 6
  "Distancia minima a la que debe estar el agente presa del depredador para cumplir su objetivo.")

(defvar *max-dist-obj* 10
  "Distancia máxima a la que debe estar el agente presa del depredador para cumplir su objetivo.")

(defvar *mejor-dist* 0
  "Variable temporal para almacenar la máxima distancia dentro de una búsqueda.")

(defvar *mejor-est* nil
  "Variable temporal para almacenar el mejor estado dentro de una búsqueda.")

(defvar estados-visitados nil
  "Almacena la lista de estados visitados en la busqueda.")

(defvar estado-actual nil
  "Almacena el estado actual de la búsqueda.")

(defvar *funcion-objetivo* nil
  "Distancia a la que debe estar el agente presa a la planta más cercana cuando está huyendo.")

(defconstant *w* 1.5
  "Constante de ponderación de la función heurística de estimación h'. *w* >= 1.0")

(defconstant *w-aaw* 1.5
  "Constante de ponderación de la función heurística de estimación h'. *w-aaw* >= 1.0")

(defvar *lon-cam* 10
  "Longitud mínima del camino que se busca en el A*.")

(defvar *min-lon-cam-obj* 5
  "Longitud minima a la que debe estar el agente presa para cumplir su objetivo.")

(defvar *max-lon-cam-obj* 15
  "Longitud máxima a la que debe estar el agente presa para cumplir su objetivo.")

(defvar *fw* nil
  "Función heurística fw' para las reglas en el algoritmo Anytime-WA*.")


;;
;; Funciones de apoyo para elaboración de reglas
;; ---------------------------------------------

(defun pos-posible-p (pos &optional dir)
  "Mira si es posible colocarse (planta o vacío) en la posición resultante de moverse en la dirección DIR a la posición POS. Devuelve algo verdadero en tal caso y NIL en caso contrario. POS es una posición del tablero dada por una lista con valor de coordenada X y valor de coordenada Y. DIR ha de ser un número entero (dirección) entre 0 y 3 (norte, este, sur y oeste respectivamente) o NIL si se quiere consultar la posición POS."
  (member (envio:consulta-tipo (envio:consulta-pos-tab pos dir)) '(envio:planta nil)))

(defconstant dir-inc
  (make-array '(4 2)
	      :initial-contents
	      '((1 -1)    ; Norte
		(0 +1)    ; Este
		(1 +1)    ; Sur
		(0 -1)))  ; Oeste
  "Array para transformar de dirección a número de coordenada a modificar y valor de incremento.")

(defmacro dir2dim-inc (dir)
  `(aref dir-inc ,dir 0))

(defmacro dir2val-inc (dir)
  `(aref dir-inc ,dir 1))

(defun pos-inc-dir (pos dir)
  "Calcula nueva lista con la posición resultante de desplazarse en la dirección DIR respecto a POS."
  (let ((pos-inc (copy-list pos)))
    (setf (nth (dir2dim-inc dir) pos-inc)
	  (+ (nth (dir2dim-inc dir) pos-inc)
	     (dir2val-inc dir)))
    pos-inc))

(defun distancia-city (pos1 pos2)
  "Calcula la distancia city block entre POS1 y POS2."
  (+ (abs (- (first pos1) (first pos2)))
     (abs (- (second pos1) (second pos2)))))

(defun dist-dpdd (pos)
  "Calcula la distancia city block desde POS hasta donde está el depredador. Si no existe depredador devuelve NIL."
  (let ((pos-dpdd (envio:consulta-pos-jug *id-dpdd*)))
    (if pos-dpdd
	(distancia-city pos pos-dpdd))))


;;
;; Funciones para generar sistema de producción
;; --------------------------------------------

(defun estados-iniciales (id)
  "Genera lista de estados iniciales del jugador con identificador ID."
  (let ((nue-est (make-estado :camino (list (envio:consulta-pos-jug id)))))
    (if *f-heur*
	(setf (estado-f-heur nue-est) (funcall *f-heur* nue-est)))
    (list nue-est)))

(defun precond-regla-dir (est dir)
  "Generador de precondicion de regla de mover el estado EST en dirección DIR."
  (let ((pos-est (first (estado-camino est))))
    ; La nueva posición no pertenece al propio camino
    (and (not (member (pos-inc-dir pos-est dir)
		      (rest (estado-camino est))
		      :test #'equal))
	 ; Y la nueva posición se puede pisar
	 (pos-posible-p pos-est dir))))

(defun accion-regla-dir (est dir)
  "Generador de acción de regla de mover el estado EST en dirección DIR."
  (let ((nue-est (make-estado :camino (cons (pos-inc-dir (first (estado-camino est)) dir)
					    (estado-camino est))
			      :lon-camino (1+ (estado-lon-camino est))
			      :dir-ini (or (estado-dir-ini est) dir)
               :celdas-vacias (if (existe-planta (pos-inc-dir (first (estado-camino est)) dir))
                                (estado-celdas-vacias est)
                                (1+ (estado-celdas-vacias est))))))

    ; Asignar valor heurísticos, si se requiere
    (if *f-heur*
      (setf (estado-f-heur nue-est) (funcall *f-heur* nue-est)))
    (if *fw*
      (setf (estado-fw nue-est) (funcall *fw* nue-est)))
    nue-est))

(defun print-camino (camino)
  "Solicita imprimir la lista de posiciones dada en CAMNIO a los agentes capaces de acpetar solicitudes tipo :punteo."
  (envio:broadcast :punteo (reverse camino)))


;;
;; Inicializador de agentes de búsqueda de camino
;; ----------------------------------------------

(defun alu2434-2517-presa-ini (id tipo-juego)
  "Inicialización genérica de agente que buscan camino."
  (declare (ignore id tipo-juego))          ; Ignorar parámetros no usados
  (if (pt-util:usa-sistema 'camino-presa)   ; Si no existían ya las reglas
      (progn
	; Insertar las nuevas reglas
	(pt-util:regla #'(lambda (est) (precond-regla-dir est 3))  ; Regla Oeste
		       #'(lambda (est) (accion-regla-dir est 3)))
	(pt-util:regla #'(lambda (est) (precond-regla-dir est 1))  ; Regla Este
		       #'(lambda (est) (accion-regla-dir est 1)))
	(pt-util:regla #'(lambda (est) (precond-regla-dir est 0))  ; Regla Norte
		       #'(lambda (est) (accion-regla-dir est 0)))
	(pt-util:regla #'(lambda (est) (precond-regla-dir est 2))  ; Regla Sur
		       #'(lambda (est) (accion-regla-dir est 2)))))
   (setf *dist-obj* 6)
  t)    ; Devolver T siempre


;;
;; Agente búsqueda de camino en anchura
;; ------------------------------------

(defun estado-objetivo-p (est)
  "Chequea si un estado EST es estado objetivo o NIL."
  ; Si se ha acabado el tiempo o no se ha encontrado solución
  (or (pt-util:consulta-contador) (null est)
      (let ((dt (dist-dpdd (first (estado-camino est)))))
	(or (not dt)              ; o no hay depredador
	    (>= dt                ; o se ha alcanzado la distancia 
		*dist-obj*)))))   ; *dist-obj* al depredador

(defun estado-objetivo-p-guarda-mejor (est)
  "Chequea si un estado EST es estado objetivo o NIL."
  ; Si se ha acabado el tiempo o no se ha encontrado solución
  ;(print "correr")
  (or
    (pt-util:consulta-contador)
    (null est)
    (let ((dt (dist-dpdd (first (estado-camino est)))))
		(if (> dt *mejor-dist*)
        (progn
          (setf *mejor-est* est)
          (setf *mejor-dist* dt)))
      (or
        (not dt)                  ; o no hay depredador
        (>= dt *dist-obj*)))))    ; o se ha alcanzado la distancia *dist-obj* al depredador

(defun f-dec-dist-obj ()
	(if (> *dist-obj* *min-dist-obj*)
		(decf *dist-obj*)))

(defun f-inc-dist-obj ()
	(if (< *dist-obj* *max-dist-obj*)
		(incf *dist-obj*)))

(defun f-dec-lon-cam-obj ()
	(if (> *lon-cam* *min-lon-cam-obj*)
		(decf *lon-cam*)))

(defun f-inc-lon-cam-obj ()
	(if (< *lon-cam* *max-lon-cam-obj*)
		(incf *lon-cam*)))

;
;Tramiento de  Estados visitados
;

(defun not-contain (est lista-estados)
  "Retorna true si 'est' no está en 'lista-estados'. En otro caso, retorna nil"
  (cond
    ((equal nil est) nil)                          ; ¿estado == nil?
    ((equal nil (estado-camino est)) nil)          ; ¿estado-camino == nil?
    ((endp lista-estados) t)                       ; ¿lista vacía?
    ((igual-estado est (first lista-estados)) nil) ; ¿est == first list? ( primer elemento )
    (t (not-contain est (rest lista-estados)))))   ; ¿est == rest list?  ( resto de la lista )

(defun ba-visitados-a-merge-fn (nuevos-estados)
  "Retorna la lista de frente filtrando los estados que pertenezcan a la lista de estados visitados."
  (let ((estados-no-cribados nil))                  ; Inicializas estados no cribados a nil
    (loop for estado in nuevos-estados do           ; recorre toda la lista 
	(if (not-contain estado estados-visitados)  ; comprueba que el estado no esta en los visitados
		(push estado estados-no-cribados))) ; Y si no está lo mete.
    (nconc pt-util:*search-queue* estados-no-cribados))) ; añade estados no cribados a la lista de frentes

;
; con cons Añade el estado al principio de  lista de visitados
;
(defun actualizar-visitados (estado)
  "Introduce el estado en la lista de visitados."
  (if (not (equal estado nil))
      ;(setf estados-visitados (cons estado estados-visitados))))
      (push  estado estados-visitados)))

;
; pt-util:*search-queue* => Lista de frente
;

(defun ba-visitados-a-dequeue-fn ()
  "Extrae el primer elemento de la lista de frente y lo introduce en la lista de visitados."
  (actualizar-visitados (setf estado-actual (pop pt-util:*search-queue*)))
  estado-actual)

;
; Búsqueda en anchura con tratamiento de estados visitados
;

(defun alu2434-2517-presa-ba-tev (id)
  "Agente jugador PlanTron que busca camino en anchura a lugar lejos de depredador."
  ;(print *dist-obj*)
  ; Iniciar contador de tiempo transcurrido
  (pt-util:inicia-contador 10)
  ; Usar sistema de producción de la presa
  (pt-util:usa-sistema 'camino-presa)
  ; Cargar heurística a utilizar (sin heurística)
  (setf estados-visitados nil)  
  (setf *f-heur* nil)
  ; Lanzar búsqueda
  (setf *mejor-dist* 0)
  (let ((est-sol
	 (pt-util:generic-search
	  (estados-iniciales id)
	  #'estado-objetivo-p-guarda-mejor
	  #'pt-util:hijos
	  :display-fn #'null
	  :merge-fn   #'ba-visitados-a-merge-fn
	  :dequeue-fn #'ba-visitados-a-dequeue-fn)))
    ; Preguntar por condiciones de parada
    (cond
     ((or (null est-sol)                    ; No encontrada solución (encerrado)
	  (null (estado-dir-ini est-sol)))  ; o estado inicial es solución
      (envio:mensaje "Lanzo espiral")
		(f-inc-dist-obj)
      (pt-agentes-simples::agente-cobarde id))    ; Como agente-espiral
     
     ((pt-util:consulta-contador) ; Agotado el tiempo de búsqueda
      (envio:mensaje "Agotado el tiempo de búsqueda")
		(f-dec-dist-obj)
      (if (pos-posible-p (first (estado-camino *mejor-est*)))
        (estado-dir-ini *mejor-est*)                   ; Mover según mejor estado
        (estado-dir-ini est-sol)))                     ; Mover según estado actual
     
     (t                           ; Encontrado camino
      (envio:mensaje "Encontrado camino BA")
		(f-inc-dist-obj)
      (print-camino (estado-camino est-sol))
      (estado-dir-ini est-sol)))))                ; Mover según estado solución

;
; Búsqueda en anchura con tratamiento de estados visitados buscando una planta en el camino
;

(defun dist-planta-cerca (pos)
  "Calcula la distancia city-block desde la posición POS a la planta más cercana a dicha posición. Si no hay plantas devuelve NIL."
  (let ((pc (first (pt-util:planta-cerca pos))))
   (if pc
      (distancia-city pos (first pc)))))

(defun estado-objetivo-planta-cerca (est)
"Chequea si un estado EST es estado objetivo o NIL."
; Si se ha acabado el tiempo o no se ha encontrado solución
(or
	(pt-util:consulta-contador)
	(null est)
	(let (	(pc (first(pt-util:planta-cerca (first (estado-camino est)))))
		;(pc1 (dist-planta-cerca (first (estado-camino est))))
		(dtm (and *mejor-est* (dist-dpdd (first (estado-camino *mejor-est*)))))
		(dt (dist-dpdd(first (estado-camino est)))))
		(if (or (null *mejor-est*)(> dt dtm))
			(setf *mejor-est* est))
			(and (or (not dt) ; o no hay depredador
				(>= dt *dist-obj*)) ; o alcanzada dist-obj al depredador
				(let((pl-cerca-ini(distancia-city (first(last (estado-camino est)))(first pc))) 
					(pl-cerca-fin(distancia-city (first (estado-camino est))(first pc))))
					(> pl-cerca-ini pl-cerca-fin)))))) ; Posición final mas cerca que 
									   ; que la inical => True


(defun alu2434-2517-presa-bap-tev (id)
  "Agente jugador PlanTron que busca camino en anchura a lugar lejos de depredador."
  ;(print *dist-obj*)
  ; Iniciar contador de tiempo transcurrido
  (pt-util:inicia-contador 10)
  ; Usar sistema de producción de la presa
  (pt-util:usa-sistema 'camino-presa)
  ; Cargar heurística a utilizar (sin heurística)
  (setf estados-visitados nil)  
  (setf *f-heur* nil)
  ; Lanzar búsqueda
  (setf *mejor-dist* 0)
  (let ((est-sol
	 (pt-util:generic-search
	  (estados-iniciales id)
	  #'estado-objetivo-planta-cerca
	  #'pt-util:hijos
	  :display-fn #'null
	  :merge-fn   #'haces-a-merge-fn
	  :dequeue-fn #'ba-visitados-a-dequeue-fn)))
    ; Preguntar por condiciones de parada
    (cond
     ((or (null est-sol)                    ; No encontrada solución (encerrado)
	  (null (estado-dir-ini est-sol)))  ; o estado inicial es solución
      (envio:mensaje "Lanzo espiral")
		(f-inc-dist-obj)
      (pt-agentes-simples::agente-espiral id))    ; Como agente-espiral
     
     ((pt-util:consulta-contador) ; Agotado el tiempo de búsqueda
      (envio:mensaje "Agotado el tiempo de búsqueda")
		(f-dec-dist-obj)
      (if (pos-posible-p (first (estado-camino *mejor-est*)))
        (estado-dir-ini *mejor-est*)                   ; Mover según mejor estado
        (estado-dir-ini est-sol)))                     ; Mover según estado actual
     
     (t                           ; Encontrado camino
      (envio:mensaje "Encontrado camino BA")
		(f-inc-dist-obj)
      (print-camino (estado-camino est-sol))
      (estado-dir-ini est-sol)))))                ; Mover según estado solución

;
; Búsqueda mediante la estrategia de Haces
;

(defun imprime-distancias (estados)
  (let ((distancias nil))
    (loop for estado in estados do
		(push (dist-dpdd (first (estado-camino estado))) distancias))
    (print distancias)))

(defun ordena-por-distancia-depredador (a b)
  (cond ((null a) (not (null b)))
    ((null b) nil)
    (t (<
      (dist-dpdd (first (estado-camino a)))
      (dist-dpdd (first (estado-camino b)))))))

(defun ordena-por-distancia-planta (a b)
  (cond ((null a) (not (null b)))
    ((null b) nil)
    (t (<
      (dist-planta-cerca (first (estado-camino a)))
      (dist-planta-cerca (first (estado-camino b)))))))

(defun haces-podar-fn (nuevos-estados)
  (let ((dt (dist-dpdd (first (estado-camino estado-actual)))))
    (if (< dt *dist-obj*)
      (reverse (cdr  (sort nuevos-estados #'ordena-por-distancia-depredador)))
      (reverse (cdr (reverse (sort nuevos-estados #'ordena-por-distancia-planta)))))))

(defun haces-a-merge-fn (nuevos-estados)
  (nconc pt-util:*search-queue* (haces-podar-fn nuevos-estados))) ; añade estados no cribados a la lista de frentes

(defun alu2434-2517-presa-hzp (id)
  "Agente jugador PlanTron que busca camino en anchura a lugar lejos de depredador."
  ;(print *dist-obj*)
  ; Iniciar contador de tiempo transcurrido
  (pt-util:inicia-contador 10)
  ; Usar sistema de producción de la presa
  (pt-util:usa-sistema 'camino-presa)
  ; Cargar heurística a utilizar (sin heurística)
  (setf estados-visitados nil)  
  (setf *f-heur* nil)
  ; Lanzar búsqueda
  (setf *mejor-dist* 0)
  (let ((est-sol
	 (pt-util:generic-search
	  (estados-iniciales id)
	  #'estado-objetivo-planta-cerca
	  #'pt-util:hijos
	  :display-fn #'null
	  :merge-fn   #'haces-a-merge-fn
	  :dequeue-fn #'ba-visitados-a-dequeue-fn)))
    ; Preguntar por condiciones de parada
    (cond
     ((or (null est-sol)                    ; No encontrada solución (encerrado)
	  (null (estado-dir-ini est-sol)))  ; o estado inicial es solución
      (envio:mensaje "Lanzo espiral")
		(f-inc-dist-obj)
      (pt-agentes-simples::agente-espiral id))    ; Como agente-espiral
     
     ((pt-util:consulta-contador) ; Agotado el tiempo de búsqueda
      (envio:mensaje "Agotado el tiempo de búsqueda")
		(f-dec-dist-obj)
      (if (pos-posible-p (first (estado-camino *mejor-est*)))
        (estado-dir-ini *mejor-est*)                   ; Mover según mejor estado
        (estado-dir-ini est-sol)))                     ; Mover según estado actual
     
     (t                           ; Encontrado camino
      (envio:mensaje "Encontrado camino BA")
		(f-inc-dist-obj)
      (print-camino (estado-camino est-sol))
      (estado-dir-ini est-sol)))))                ; Mover según estado solución

;;
;; Agente búsqueda de camino A*
;; ----------------------------

(defun existe-planta (pos)
  "Devuelve T or False sí en pos existe o no una planta"
  (eq (envio:consulta-tipo (envio:consulta-pos-tab pos)) 'envio:planta))

(defun f-dist-dpdd (est)
  "Función heurística subdividida con coste del camino acumulado + distancia estimada por city block que falta para alejarse hasta *dist-obj* del depredador."
  (let ((dt (dist-dpdd (first (last (estado-camino est))))))
    (+ (estado-lon-camino est)
      (if dt
        (- *dist-obj* dt)                         ; El agente tiene que huir del depredador
        0))))

(defun calcula-h-comer (est)
  (let
    ((plantas-en-radio 0)
    (camino-por-recorrer (- *lon-cam* (estado-lon-camino est))))
    (loop for planta in (pt-util:planta-cerca (first (estado-camino est)) camino-por-recorrer) do
;      (format t "Dis:    ~d    ~d ~%" (distancia-city (first planta) (first (estado-camino est))) planta)
		(if (< (distancia-city (first planta) (first (estado-camino est))) camino-por-recorrer)
        (incf plantas-en-radio)))
;    (format t "Resumen:       ~d   ~d ~d ~%" (first (estado-camino est)) camino-por-recorrer plantas-en-radio)
    (- camino-por-recorrer plantas-en-radio)))

(defun f-dist-comer (est)
  "Función heurística subdividida con coste del camino acumulado + distancia estimada por city block que falta para alejarse hasta *dist-obj* del depredador."
  (+ (estado-celdas-vacias est) (* *w* (calcula-h-comer est))))

(defun estado-objetivo-huir-a-p (est)
  "Chequea si un estado EST es estado objetivo o NIL. Aprovecha el campo F-HEUR del estado."
  ; Si se ha acabado el tiempo o no se ha encontrado solución
  (setf *mejor-est* est)
  (or
    (pt-util:consulta-contador)
    (null est)
    (>= (estado-lon-camino est) (estado-f-heur est))  ; o ya se ha separado
    (>= (estado-lon-camino est) *lon-cam*)))           ; la longitud del camino supera a lon-cam

(defun estado-objetivo-comer-a-p (est)
  "Chequea si un estado EST es estado objetivo o NIL. La longitud del camino hasta ese estado debe ser igual a lon-cam."
  ; Si se ha acabado el tiempo o no se ha encontrado solución
  (setf *mejor-est* est)
  (or
    (pt-util:consulta-contador)
    (null est)
    (= (estado-lon-camino est) *lon-cam*)))       ; la longitud del camino es igual a lon-cam

(defun set-func-huir ()
  (setf *estado-objetivo-a-p* #'estado-objetivo-huir-a-p)
  (setf *f-heur* #'f-dist-dpdd)                             ; Fun. f' para reglas
  (setf pt-util:*coste-acum-fn* #'estado-lon-camino)        ; Fun. g  para búsqueda
  (setf pt-util:*eval-fn* #'estado-f-heur))                 ; Fun. f' para búsqueda

(defun set-func-comer ()
  (setf *estado-objetivo-a-p* #'estado-objetivo-comer-a-p)
  (setf *f-heur* #'f-dist-comer)                            ; Fun. f' para reglas
  (setf pt-util:*coste-acum-fn* #'estado-celdas-vacias)     ; Fun. g  para búsqueda
  (setf pt-util:*eval-fn* #'estado-f-heur))                 ; Fun. f' para búsqueda

(defun set-func (pos)
  (let ((dt (dist-dpdd pos)))
    (if dt
      (if (< dt *dist-obj*)
        (set-func-huir)
        (set-func-comer))
      (set-func-comer))))

(defun igual-estado (est1 est2)
  "Comprueba si el estado EST1 es igual al EST2"
  ; Considerar dos estados iguales si su camino
  ; acaba en la misma posición
  (equal (first (estado-camino est1))
         (first (estado-camino est2))))

(defun alu2434-2517-presa-awp (id)
  "Agente jugador PlanTron que busca con algoritmo A camino a lugar lejos de depredador."
  ; Iniciar contador de tiempo
  (pt-util:inicia-contador 15)
  ; Usar sistema de producción de la presa
  (pt-util:usa-sistema 'camino-presa)
  ; Inicializar variables para heurísticas del A*
  (set-func (envio:consulta-pos-jug id))
  (setf pt-util:*igual-est-fn* #'igual-estado)        ; Pred. estados iguales

  ; Lanzar búsqueda
  (let ((est-sol
	 (pt-util:generic-search
	  (estados-iniciales id)
	  *estado-objetivo-a-p*
	  #'pt-util:hijos
	  :display-fn #'null
	  :merge-fn   #'pt-util:priority-a-merge-fn
	  :dequeue-fn #'pt-util:priority-a-dequeue-fn)))
    ; Preguntar por condiciones de parada
    (cond
     ((or (null est-sol)                    ; No encontrada solución (encerrado)
	  (null (estado-dir-ini est-sol)))  ; o estado inicial es solución
      (envio:mensaje "Lanzo espiral")
		(f-inc-dist-obj)
		(f-inc-lon-cam-obj)
      (pt-agentes-simples::agente-espiral id))    ; Como agente-espiral

     ((pt-util:consulta-contador) ; Agotado el tiempo de búsqueda
      (envio:mensaje "Agotado el tiempo de búsqueda")
		(f-dec-dist-obj)
		(f-dec-lon-cam-obj)
      (if (pos-posible-p (first (estado-camino *mejor-est*)))
        (estado-dir-ini *mejor-est*)                   ; Mover según mejor estado
          (estado-dir-ini est-sol)))                   ; Mover según estado actual  
   
     (t                           ; Encontrado camino
      (envio:mensaje "Encontrado camino A*")
		(f-inc-dist-obj)
		(f-inc-lon-cam-obj)
      (print-camino (estado-camino est-sol))
      (estado-dir-ini est-sol)))))                ; Mover según estado solución

;;
;; Agente búsqueda de camino Anytime Weighted A*
;; ----------------------------

(defun estado-objetivo-huir-aawp (est)
  "Chequea si un estado EST es estado objetivo o NIL. Aprovecha el campo F-HEUR del estado."
  ; Si se ha acabado el tiempo o no se ha encontrado solución
  (or
    (pt-util:consulta-contador)
    (null est)
    (>= (estado-lon-camino est) (estado-f-heur est))  ; o ya se ha separado
    (>= (estado-lon-camino est) *lon-cam*)))           ; la longitud del camino supera a lon-cam

(defun estado-objetivo-comer-aawp (est)
  "Chequea si un estado EST es estado objetivo o NIL. La longitud del camino hasta ese estado debe ser igual a lon-cam."
  ; Si se ha acabado el tiempo o no se ha encontrado solución
;  (format t "Dis:    ~d    ~d ~%" (estado-lon-camino est) *lon-cam*)
  (or
    (pt-util:consulta-contador)
    (null est)
    (= (estado-lon-camino est) *lon-cam*)))       ; la longitud del camino es igual a lon-cam

(defun f-dist-dpdd-aawp (est)
  "Función heurística subdividida con coste del camino acumulado + distancia estimada por city block que falta para alejarse hasta *dist-obj* del depredador."
  (let ((dt (dist-dpdd (first (last (estado-camino est))))))
    (+ (estado-lon-camino est)
      (if dt
        (- *dist-obj* dt)                         ; El agente tiene que huir del depredador
        0))))

(defun fw-dist-dpdd-aawp (est)
  "Función heurística subdividida con coste del camino acumulado + distancia estimada por city block que falta para alejarse hasta *dist-obj* del depredador."
  (let ((dt (dist-dpdd (first (last (estado-camino est))))))
    (+ (estado-lon-camino est)
      (if dt
        (* *w-aaw* (- *dist-obj* dt))                        ; El agente tiene que huir del depredador
        0))))

(defun calcula-h-comer-aawp (est)
  (let
    ((plantas-en-radio 0)
    (camino-por-recorrer (- *lon-cam* (estado-lon-camino est))))
    (loop for planta in (pt-util:planta-cerca (first (estado-camino est)) camino-por-recorrer) do
;      (format t "Dis:    ~d    ~d ~%" (distancia-city (first planta) (first (estado-camino est))) planta)
		(if (< (distancia-city (first planta) (first (estado-camino est))) camino-por-recorrer)
        (incf plantas-en-radio)))
;    (format t "Resumen:       ~d   ~d ~d ~%" (first (estado-camino est)) camino-por-recorrer plantas-en-radio)
    (- camino-por-recorrer plantas-en-radio)))

(defun f-heur-comer-aawp (est)
 (+ (estado-celdas-vacias est) (estado-lon-camino est) (calcula-h-comer-aawp est)))

(defun fw-heur-comer-aawp (est)
  (+ (estado-celdas-vacias est) (estado-lon-camino est) (* *w-aaw* (calcula-h-comer-aawp est))))

(defun set-func-huir-aawp ()
  (setf *estado-objetivo-aaw-p* #'estado-objetivo-huir-aawp)
  (setf *fw* #'fw-dist-dpdd-aawp)                           ; Fun. fw' para reglas
  (setf *f-heur* #'f-dist-dpdd-aawp)                        ; Fun. f' para reglas
  (setf pt-util:*coste-acum-fn* #'estado-lon-camino)        ; Fun. g  para búsqueda
  (setf pt-util:*eval-fn* #'estado-f-heur))                 ; Fun. f' para búsqueda

(defun set-func-comer-aawp ()
  (setf *estado-objetivo-aaw-p* #'estado-objetivo-comer-aawp)
  (setf *fw* #'fw-heur-comer-aawp)                    	   ; Fun. fw' para reglas
  (setf *f-heur* #'f-heur-comer-aawp)                       ; Fun. f' para reglas
  (setf pt-util:*coste-acum-fn* #'estado-celdas-vacias)     ; Fun. g  para búsqueda
  (setf pt-util:*eval-fn* #'estado-f-heur))                 ; Fun. f' para búsqueda

(defun set-func-aawp (pos)
  (let ((dt (dist-dpdd pos)))
    (if dt
      (if (< dt *dist-obj*)
        (set-func-huir-aawp)
        (set-func-comer-aawp))
      (set-func-comer-aawp))))

(defun anytime-weighted-a (new-states)
  (let ((states nil))
    (loop for est in new-states do
      (if (or (null *mejor-est*) (< (estado-f-heur estado-actual) (estado-f-heur *mejor-est*)))
        (if (funcall *estado-objetivo-aaw-p* est)
          (progn
            (setf *mejor-est* est)
            (setf (estado-f-heur est) (funcall pt-util:*coste-acum-fn* est))
          )
          (progn 
            (push est states)
          )
        )))
    states))

(defun priority-merge-fn-aaw-p (new-states)
  "Fusiona la lista de hijos (NEW-STATES) a la lista de frente (GENERIC-SEARCH:*SEARCH-QUEUE*), manténiendola ordenada segun f' (GENERIC-SEARCH:*EVAL-FN*) y eliminando los peores estados de los duplicados."
  ; Para los hijos de la lista de hijos que sean objetivo, asigna g y f', además de coger el mejor estado.
  (setf new-states (anytime-weighted-a new-states))
  ; Chequea y criba si los estados hijos ya estan en la lista de frente de una u otra lista
  (setf new-states (pt-util:criba-iguales new-states))
  ; Ordena los estados hijos en función de fw'
  (setf new-states (sort new-states #'< :key #'estado-fw))
  ; Realiza fusión ordenada de hijos en lista frente
  (pt-util:fusion new-states generic-search:*search-queue*))

(defun priority-a-dequeue-fn-aaw-p ()
  "Función que extrae el primer elemento de la lista de frente (GENERIC-SEARCH:*SEARCH-QUEUE*) creada con PRIORITY-A-MERGE-FN devolviendo un estado."
  (setf estado-actual (pop generic-search:*search-queue*))
  estado-actual)

(defun alu2434-2517-presa-aawp (id)
  "Agente jugador PlanTron que busca con algoritmo A camino a lugar lejos de depredador."
  ; Iniciar contador de tiempo
  (pt-util:inicia-contador 15)
  ; Usar sistema de producción de la presa
  (pt-util:usa-sistema 'camino-presa)
  ; Inicializar variables para heurísticas del AAW*
  (set-func-aawp (envio:consulta-pos-jug id))
  (setf pt-util:*igual-est-fn* #'igual-estado) 
  (setf *mejor-est* nil)

  (pt-util:generic-search
    (estados-iniciales id)
    #'(lambda (est) (or (pt-util:consulta-contador) (null est)))
    #'pt-util:hijos
    :display-fn #'null
    :merge-fn   #'priority-merge-fn-aaw-p
    :dequeue-fn #'priority-a-dequeue-fn-aaw-p)

    ; Preguntar por condiciones de parada
    (cond
     ((null *mejor-est*)                    ; No encontrada solución (encerrado)
      (envio:mensaje "Lanzo espiral")
		(f-inc-dist-obj)
		(f-inc-lon-cam-obj)
      (pt-agentes-simples::agente-espiral id))    ; Como agente-espiral

     ((pt-util:consulta-contador) ; Agotado el tiempo de búsqueda
      (envio:mensaje "Agotado el tiempo de búsqueda")
		(f-dec-dist-obj)
		(f-dec-lon-cam-obj)
      (estado-dir-ini *mejor-est*))                   ; Mover según estado actual
     (t                           ; Encontrado camino
      (envio:mensaje "Encontrado camino AAW*")
		(f-inc-dist-obj)
		(f-inc-lon-cam-obj)
      (estado-dir-ini *mejor-est*))))                ; Mover según estado solución

;;
;; Definiciones de agentes presentes en este package
;; -------------------------------------------------

(pt:defagente alu2434-2517-presa-ba-tev
	      :turno #'alu2434-2517-presa-ba-tev
	      :inicio #'alu2434-2517-presa-ini
	      :use '("CONTADOR" "SHELL" "GENERIC-SEARCH")
	      :documentation "Agente jugador PlanTron que busca camino en anchura a lugar lejos de depredador con tratamiento de estados visitados.")

(pt:defagente alu2434-2517-presa-bap-tev
	      :turno #'alu2434-2517-presa-bap-tev
	      :inicio #'alu2434-2517-presa-ini
	      :use '("CONTADOR" "SHELL" "PLANTA-CERCA" "GENERIC-SEARCH")
	      :documentation "Agente jugador PlanTron que busca camino en anchura a lugar lejos de depredador con tratamiento de estados visitados y buscando una planta.")

(pt:defagente alu2434-2517-presa-hzp
	      :turno #'alu2434-2517-presa-hzp
	      :inicio #'alu2434-2517-presa-ini
	      :use '("CONTADOR" "SHELL" "PLANTA-CERCA" "GENERIC-SEARCH")
	      :documentation "Agente jugador PlanTron que busca camino por haces a lugar lejos de depredador con tratamiento de estados visitados y buscando una planta.")

(pt:defagente alu2434-2517-presa-awp
	      :turno #'alu2434-2517-presa-awp
	      :inicio #'alu2434-2517-presa-ini
	      :use '("CONTADOR" "SHELL" "PLANTA-CERCA" "GENERIC-SEARCH" "A_STAR")
	      :documentation "Agente jugador PlanTron que busca camino con algoritmo A a lugar lejos de depredador.")

(pt:defagente alu2434-2517-presa-aawp
	      :turno #'alu2434-2517-presa-aawp
	      :inicio #'alu2434-2517-presa-ini
	      :use '("CONTADOR" "SHELL" "PLANTA-CERCA" "GENERIC-SEARCH" "A_STAR")
	      :documentation "Agente jugador PlanTron que busca camino con algoritmo Anytime WA a lugar lejos de depredador.")

